import java.util.Deque;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-02-02
 * Time: 21:57
 */

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        if(p == root || q == root) {
            return root;
        }
        TreeNode leftRet = lowestCommonAncestor(root.left,p,q);
        TreeNode rightRet = lowestCommonAncestor(root.right,p,q);
        if(leftRet != null && rightRet != null) {
            return root;
        }else if(leftRet != null) {
            return leftRet;
        }else if(rightRet != null) {
            return rightRet;
        }
        return null;
    }

    //第二种方法，放入栈中，找根到该结点的路径，并存放在栈中
    public boolean getPath(TreeNode root, TreeNode node, Deque<TreeNode> stack) {
        if(root == null || node == null) {
            return false;
        }
        stack.push(root);
        //放完之后要检查是否为node
        if(root == node) {
            return true;
        }
        boolean ret1 = getPath(root.left,node,stack);
        if(ret1 == true) {
            return true;
        }
        boolean ret2 = getPath(root.right,node,stack);
        if(ret2 == true) {
            return true;
        }
        stack.pop();
        return false;
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        //1.两个栈中存储好数据
        Deque<TreeNode> stack1 = new LinkedList<>();
        getPath(root,p,stack1);
        Deque<TreeNode> stack2 = new LinkedList<>();
        getPath(root,q,stack2);
        //2.判断栈的大小
        int size1 = stack1.size();
        int size2 = stack2.size();

        if(size1 > size2) {
            int size = size1-size2;
            while(size != 0) {
                stack1.pop();
                size--;
            }
        }else {
            int size = size2 - size1;
            while(size != 0) {
                stack2.pop();
                size--;
            }
        }
        //找数据个数是一样
        while(!stack1.isEmpty() && !stack2.isEmpty()) {
            if(stack1.peek() != stack2.peek()) {
                stack1.pop();
                stack2.pop();
            }else {
                return stack1.peek();
            }
        }
        return null;
    }
}
